package com.zjj.lbw.algorithm.adt;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author zhanglei.zjj
 * @description leetcode_128. 最长连续序列，哈希表求解 & 并查集求解
 * @date 2023/6/11 18:02
 */
public class LongestConsecutiveSeq_leetcode_128 {
    // 哈希表求解
    public int longestConsecutive1(int[] nums) {
        Set<Integer> set = new HashSet();
        for (int num : nums) {
            set.add(num);
        }
        int maxLength = 0;
        for (int num : set) {
            int cur = num;
            // 如果当前元素 -1 不在哈希表中才往下找连续元素
            // 因为如果在hash表中遍历到这个 元素时，一定会找到当前元素，且比当前元素往后找出的连续序列更长
            if (!set.contains(cur - 1)) {
                while (set.contains(cur + 1)) {
                    cur++;
                }
            }
            maxLength = Math.max(maxLength, cur - num + 1);
        }

        return maxLength;
    }

    // 并查集求解
    public int longestConsecutive(int[] nums) {
        ADT adt = new ADT(nums);
        for (int num : nums) {
            // 如果当前元素 + 1的元素存在，则以当前元素 + 1为父元素构建集合
            if (adt.find(num + 1) != null) {
                adt.union(num, num + 1);
            }
        }
        int max = 0;
        for (int num : nums) {
            int root = adt.find(num);
            max = Math.max(max, root - num + 1);
        }

        return max;
    }
}

class ADT {
    // 记录每个元素的父节点，key为当前节点，value为父节点
    private Map<Integer, Integer> parent = new HashMap<>();

    public ADT(int[] nums) {
        for (int num : nums) {
            // 最开始 每个元素自己就是一个集合，认为它的父结点都是本身
            parent.put(num, num);
        }
    }

    // 寻找 num的根结点
    public Integer find(int num) {
        if (!parent.containsKey(num)) {
            return null;
        }
        // 遍历num的父结点，parent.get(num) != num 说明num有父结点
        // 当等于时，说明当前元素的根结点是自己，则退出循环
        while (parent.get(num) != num) {
            // 让祖父结点成为num的父结点，进行指针压缩
            parent.put(num, parent.get(parent.get(num)));
            // 从num的最新父结点开始遍历
            num = parent.get(num);
        }

        return num;
    }

    // 合并两个集合，将childA加入到chidB的连续区间中
    public void union(int childA, int childB) {
        int rootA = find(childA);
        int rootB = find(childB);
        // childA 和 ChildB已经属于同一连续区间中
        if (rootA == rootB) {
            return;
        }
        parent.put(rootA, rootB);
    }

}
